#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 510;
const int M = 1510;
const int inf = 0x3f3f3f3f;

int f[11][N], g[11][N], n, m, u[M], v[M], w[M], dep[N];
veg G[N];

namespace F { // max_flow
	const int N = 510;
	const int M = 6010;
    int h[N], now[N], d[N], cnt = 1, S, T;
    struct edge { int v, w, nxt; } e[M << 1];
    inline void tlink(int x, int y, int w) { e[++cnt] = (edge) { y, w, h[x] }; h[x] = cnt; }
    inline void link(int x, int y, int w) { tlink(x, y, w); tlink(y, x, 0); }
    inline void setst(int s, int t) { S = s; T = t; }
    queue < int > q;
	void reset() { rep(i, 0, n) h[i] = 0; cnt = 1; }
    bool bfs() {
		while(q.size()) q.pop(); q.push(S); memset(d, 0, sizeof d); d[S] = 1; now[S] = h[S];
		while(!q.empty()) {
			int x = q.front(); q.pop();
			for(int i = h[x], y; i; i = e[i].nxt)
				if(e[i].w && !d[y = e[i].v]) {
					d[y] = d[x] + 1; q.push(y); now[y] = h[y];
					if(y == T) return 1;
				}
		} return 0;
    }
    int dinic(int x, int flow) {
		if(x == T) return flow;
		int res = flow;
		for(int i = now[x], y; i && res; i = e[i].nxt) {
			now[x] = i;
			if(e[i].w && d[y = e[i].v] == d[x] + 1) {
				int k = dinic(y, min(res, e[i].w));
				if(!k) d[y] = 0; e[i].w -= k; e[i ^ 1].w += k; res -= k;
			}
		}
		return flow - res;
    }
    ll runit() {
		ll maxflow = 0,flow;
		while(bfs()) while(flow = dinic(S, inf)) maxflow += flow;
		return maxflow;
    }
}

int get(int x, int y) { F :: reset(); F :: setst(x, y); rep(i, 1, m) F :: link(u[i], v[i], w[i]), F :: link(v[i], u[i], w[i]); return F :: runit(); }

int p[N], q[N], top, top2 = 0;
int cnt = 0;

void build(int l, int r) {
	if(l == r) return; int x = p[l], y = p[r], w = get(x, y);
	G[x].eb(y, w); G[y].eb(x, w);
	top = 0, top2 = l; rep(i, l, r) if(!F :: d[p[i]]) q[++top] = p[i]; else  p[top2++] = p[i];
	int cur = r; while(top) p[cur--] = q[top--];
	build(l, cur); build(cur + 1, r);
}

void dfs(int x, int p) {
	dep[x] = dep[p] + 1; f[0][x] = p; rep(i, 1, 9) f[i][x] = f[i - 1][f[i - 1][x]], g[i][x] = min(g[i - 1][x], g[i - 1][f[i - 1][x]]);
	for(auto v : G[x]) if(v.fi ^ p) {
			g[0][v.fi] = v.se; dfs(v.fi, x);
		}
}

int solve(int x, int y) {
	x++, y++; int res = inf; if(dep[x] < dep[y]) swap(x, y);
	per(i, 9, 0) if(dep[f[i][x]] >= dep[y]) chkmin(res, g[i][x]), x = f[i][x];
	if(x == y) return res;
	per(i, 9, 0) if(f[i][x] != f[i][y]) chkmin(res, g[i][x]), chkmin(res, g[i][y]), x = f[i][x], y = f[i][y];
	return min({ g[0][x], res, g[0][y] });
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in + 1, m = in; rep(i, 1, m) u[i] = in + 1, v[i] = in + 1, w[i] = in;
	rep(i, 1, n) p[i] = i; 
	build(1, n); g[0][1] = inf; dfs(1, 0);
	int q = in; while(q--) printf("%d\n", solve(in, in));
	return 0;
}
